package 剑指Offer专项突破;

import test0ne.TreeNode;

import java.util.*;

/**
 * 二叉树剪枝
 */
public class Algo47 {

    /**
     * Offer50 向下的路径节点之和， 的路径的数目
     * 不止是从根节点下来的， 任何路径都算
     * @param root
     * @param targetSum
     * @return
     */
    private static Integer result = 0;
    public static int pathSum(TreeNode root, int targetSum) {
        pathSumChild(root, 0, targetSum);
        return result;
    }

    private static void pathSumChild(TreeNode root, int rootVal, int targetSum) {
        if(root == null) {return;}

        rootVal += root.val;
        if(rootVal== targetSum) {
            result++;
        }else if(rootVal < targetSum){
            pathSumChild(root.left, rootVal, targetSum);
            pathSumChild(root.right, rootVal, targetSum);
        }
        pathSumChild(root.left, 0, targetSum);
        pathSumChild(root.right, 0, targetSum);
    }

    public TreeNode pruneTree(TreeNode root) {
        jianzhi(root);
        return root;
    }

    private boolean jianzhi(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean cur = root.val == 0;
        boolean right = jianzhi(root.right);
        boolean left = jianzhi(root.left);
        if(right) {
            root.right = null;
        }
        if(left) {
            root.left = null;
        }
        return cur && right && left;
    }


    /**
     * Offer49  根节点到叶子节点的所有路径之和
     * @param root
     * @return
     */
    static List<Integer> list = new ArrayList<>();
    public static int sumNumbers(TreeNode root) {
        dfs(root, "");
        return list.stream().mapToInt(Integer::intValue).sum();
    }

    private static void dfs(TreeNode root, String s) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right==null) {
            list.add(Integer.valueOf(s+root.val));
            return;
        }
        s += root.val;
        if(root.left != null) {
            dfs(root.left, s);
        }
        if(root.right!= null) {
            dfs(root.right, s);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(9);
        root.right = new TreeNode(0);

        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(1);
//        System.out.println(pathSum(root, 13));


        TreeNode one = TreeNode.buildTreeNode(new Integer[]{-1,0,1});
//        System.out.println(pathSum(one, 22));

        Algo47 algo47 = new Algo47();
        String s = algo47.serialize(one);
        System.out.println(s);
        TreeNode treeNode = algo47.deserialize(s);
        TreeNode.printTreeNode(treeNode);
    }

    /**
     * Offer48 树的序列化和反序列化
     * @param root
     * @return
     */
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeTraver(root, sb);
        return sb.toString().substring(0, sb.length()-1);
    }

    private void serializeTraver(TreeNode root, StringBuilder sb) {
        if(root == null) {
            sb.append("#").append(",");
            return;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            TreeNode cur = list.poll();
            if(cur == null) {
                sb.append("#").append(",");
                continue;
            }else {
                sb.append(cur.val).append(",");
            }
            list.add(cur.left);
            list.add(cur.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length() == 0) {
            return null;
        }
        String[] strArr = data.split(",");
        if(data.length() == 1 && "#".equals(strArr[0])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strArr[0]));
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        int index = 1;
        while (!list.isEmpty()) {
            TreeNode cur = list.poll();
            if(cur == null) {
                continue;
            }
            String curStr = strArr[index++];
            cur.left = "#".equals(curStr)? null: new TreeNode(Integer.parseInt(curStr));
            list.add(cur.left);
            if(index == strArr.length) {
                break;
            }
            curStr = strArr[index++];
            cur.right = "#".equals(curStr)? null: new TreeNode(Integer.parseInt(curStr));
            list.add(cur.right);

        }
        return root;
    }
}
